#include "main.h"


// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
void _create_tree(BiTreeNode * root_pp, char * pre_order_seq, int *current_index, int num_elements) {
    if (*current_index >= num_elements){
        return;
    } else {
        root_pp->data = pre_order_seq[*current_index];
        *current_index += 1;
    }
    if (pre_order_seq[*current_index] == '#') {
        root_pp->leftChild = NULL;
        *current_index += 1;
    } else {
        root_pp->leftChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        _create_tree(root_pp->leftChild, pre_order_seq, current_index, num_elements);
    }
    if (pre_order_seq[*current_index] == '#') {
        root_pp->rightChild = NULL;
        *current_index += 1;
    } else {
        root_pp->rightChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        _create_tree(root_pp->rightChild, pre_order_seq, current_index, num_elements);
    }
}


void create_tree(BiTreeNode **root_pp, char *pre_order_seq, int num_elements) {
    *root_pp = (BiTreeNode *) malloc(sizeof(BiTreeNode));
    BiTreeNode *root = *root_pp;
    if (pre_order_seq[0] != '#') {
        root->data = pre_order_seq[0];
    }
    int current_index = 0;
    _create_tree(*root_pp, pre_order_seq, &current_index, num_elements);
}

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item)) {
    if (t != NULL) {
        visit(t->data);
        pre_order_traverse(t->leftChild, visit);
        pre_order_traverse(t->rightChild, visit);
    }
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item)) {
    if (t == NULL) {
        return;
    }
    in_order_traverse(t->leftChild, visit);
    visit(t->data);
    in_order_traverse(t->rightChild, visit);
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item)) {
    if (t == NULL) {
        return;
    }
    post_order_traverse(t->leftChild, visit);
    post_order_traverse(t->rightChild, visit);
    visit(t->data);
}

// 可以无需更改本函数的实现
void Visit(DataType item) {
    printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode *search(BiTreeNode *root, DataType x) {
    BiTreeNode *find = NULL;
    if (root == NULL) {
        return NULL;
    }
    if (root->data == x) {
        return root;
    } else {
        find = search(root->leftChild, x);
        if (find) {
            return find;
        }
        find = search(root->rightChild, x);
        if (find) {
            return find;
        }
    }
    return find;
}

// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root) {
    if ((*root) != NULL) {
        if ((*root)->leftChild) {
            destroy(&(*root)->leftChild);
            (*root)->leftChild = NULL;
        }
        if ((*root)->rightChild) {
            destroy(&(*root)->rightChild);
            (*root)->rightChild = NULL;
        }
        if ((*root) != NULL) {
            free((*root));
            (*root) = NULL;
        }
    }
}


int main() {
    BiTreeNode *root;
    char x='A';
    char *pre_order_seq = "ABC##DE#G##F###";
    create_tree(&root, pre_order_seq, 15);
    printf("前序遍历为：");
    pre_order_traverse(root, visit);
    printf("\n中序遍历为：");
    in_order_traverse(root,visit);
    printf("\n后序遍历为：");
    post_order_traverse(root,visit);
    search(root,x);
    printf("\n数据元素%c在二叉树中 \n",x);
    destroy(&root);
}
